Hnoi2015接水果

发表于
字数统计: 2,213字 | 阅读时长 ≈ 11min

[HNOI2015]接水果

问题描述

风见幽香非常喜欢玩一个叫做 osu!的游戏，其中她最喜欢玩的模式就是接水果。由于她已经DT FC 了The big black, 她觉得这个游戏太简单了，于是发明了一个更加难的版本。首先有一个地图，是一棵由 n 个顶点、n-1 条边组成的树（例如图 1给出的树包含 8 个顶点、7 条边）。这颗树上有 P 个盘子，每个盘子实际上是一条路径（例如图 1 中顶点 6 到顶点 8 的路径），并且每个盘子还有一个权值。第 i 个盘子就是顶点a_i到顶点b_i的路径(由于是树，所以从a_i到b_i的路径是唯一的)，权值为c_i。接下来依次会有Q个水果掉下来，每个水果本质上也是一条路径，第i 个水果是从顶点 u_i 到顶点v_i 的路径。幽香每次需要选择一个盘子去接当前的水果：一个盘子能接住一个水果，当且仅当盘子的路径是水果的路径的子路径（例如图1中从 3到7 的路径是从1到8的路径的子路径）。这里规定:从a 到b的路径与从b到 a的路径是同一条路径。当然为了提高难度，对于第 i 个水果，你需要选择能接住它的所有盘子中，权值第 k_i 小的那个盘子，每个盘子可重复使用（没有使用次数的上限：一个盘子接完一个水果后，后面还可继续接其他水果，只要它是水果路径的子路径）。幽香认为这个游戏很难，你能轻松解决给她看吗？

img

输入格式

第一行三个数 n和P 和Q，表示树的大小和盘子的个数和水果的个数。

接下来n-1 行，每行两个数 a、b，表示树上的a和b 之间有一条边。树中顶点按1到 n标号。 接下来 P 行，每行三个数 a、b、c，表示路径为 a 到 b、权值为 c 的盘子，其中0≤c≤10^9，a不等于b。

接下来Q行，每行三个数 u、v、k，表示路径为 u到 v的水果，其中 u不等于v，你需要选择第 k小的盘子，第k 小一定存在。

输出格式

对于每个果子，输出一行表示选择的盘子的权值。

样例输入

10 10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
3 2 217394434
10 7 13022269
6 7 283254485
6 8 333042360
4 6 442139372
8 3 225045590
10 4 922205209
10 8 808296330
9 2 486331361
4 9 551176338
1 8 5
3 8 3
3 8 4
1 8 3
4 8 1
2 3 1
2 3 1
2 3 1
2 4 1
1 4 1

样例输出

442139372
333042360
442139372
283254485
283254485
217394434
217394434
217394434
217394434
217394434

提示

对于所有数据，N,P,Q≤40000

求这种第$k$小的题目，一般涉及平衡树、主席树、树套树、整体二分（貌似之前见到过一个网络流+二分答案的）。这道题一眼看上去可能是整体二分。

不管怎么做，一个无法避免的问题是判断一条路径是否是另一条的子路径。如果直接思考能装下水果的盘子是哪些，即一条路径的子路径有哪些，那么显然只要把路径上的点全部拿出来，只要路径的两个端点都在其中即可。然而这样做似乎并不好处理。

不如换个角度思考，一个盘子能接住哪些水果，即一条路径会成为哪些路径的子路径。这里需要分两种情况讨论：

无标题

1.路径端点的LCA不是路径端点。这个时候，水果的两个端点必然分别在以两个路径端点为根的子树中。

2.路径端点的LCA是其中一个路径端点。这时水果的一个端点在图中红色端点的子树中，另一个则在绿色点（蓝色端点在这条路径上的儿子）为根的子树之外。

不管是哪种情况，判断一个点是否在另一个点为根的子树中都可以用DFS序解决。如果把水果路径端点的DFS序先小后大地写成二元组的形式，那么可以将其看成一个点，将盘子的DFS序表示的管辖范围看成矩形，盘子的权值就是矩形的权值。那么问题就转换为了求覆盖某个点的矩形中权值第$k$小的。这样就可以扫描线+整体二分解决了。

具体地说，设能覆盖某个点的矩形中第$k$小的是权值从小到大第$mid$个矩形，那么就只考虑前$mid$个矩形，利用扫描线求出这个点被覆盖了几次。如果覆盖次数$<k$，则说明答案在$[mid+1,r]$中；否则答案在$[l,mid]$中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define MAXN 200005
#define MAXM 400005
using namespace std;

char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R(){
	char s=GC;int sign=0,v=0;
	while((s!='-')&&(s>57||s<48))s=GC;
	if(s=='-')s=GC,sign=1;
	for(;s>47&&s<58;s=GC)v=v*10+s-48;
	return sign?-v:v;
}

int N,P,Q,Ans[MAXN];

struct rec{
	int l,r,d,u,v;
	rec(int ll=0,int rr=0,int dd=0,int uu=0,int vv=0){
		l=ll;r=rr;u=uu;d=dd;v=vv;
		if(l>d)swap(l,d),swap(r,u);
		else if(l==d&&r>u)swap(r,u);
	}
}A[MAXN*2];int cnt;

struct node{
	int u,v,k,id;
};

struct line{
	int l,d,u,k,id;
}L[MAXN];
bool operator<(line a,line b){
	return a.l==b.l?a.id<b.id:a.l<b.l;
}

bool cmpv(rec a,rec b){
	return a.v<b.v;
}

bool cmpp(rec a,rec b){
	return a.l==b.l?a.r<b.r:a.l<b.l;
}

int en[MAXM],nex[MAXM],las[MAXN],tot;
void Add(int x,int y){
	en[++tot]=y;
	nex[tot]=las[x];
	las[x]=tot;
}

int fa[MAXN][17],dep[MAXN],In[MAXN],Out[MAXN],VT;
void DFS(int x,int f){
	int i,y;
	In[x]=++VT;
	dep[x]=dep[f]+1;fa[x][0]=f;
	for(i=1;i<17;i++)fa[x][i]=fa[fa[x][i-1]][i-1];
	for(i=las[x];i;i=nex[i]){
		y=en[i];if(y==f)continue;
		DFS(y,x);
	}
	Out[x]=VT;
}

int LCA(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	int d=dep[x]-dep[y],i;
	for(i=0;i<17;i++)if(d>>i&1)x=fa[x][i];
	if(x==y)return x;
	for(i=16;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}

int gf(int x,int d){
	for(int i=0;i<17;i++)if(d>>i&1)x=fa[x][i];
	return x;
}

int C[MAXN];
void Modify(int x,int k){
	for(int i=x;i<=N;i+=(i&-i))C[i]+=k;
}
int GetSum(int x){
	int i,ret=0;
	for(i=x;i;i^=(i&-i))ret+=C[i];
	return ret;
}

vector<node>qry;

void Solve(int l,int r,vector<node>T){
	if(l==r){
		for(int i=0;i<T.size();i++)Ans[T[i].id]=A[l].v;
		return;
	}
	int i,mid=l+r>>1,cnt=0,t;
	vector<node>Q1,Q2;
	for(i=l;i<=mid;i++){
		L[++cnt]=(line){A[i].l,A[i].d,A[i].u,1,0};
		L[++cnt]=(line){A[i].r,A[i].d,A[i].u,-1,N+P+Q};
	}
	for(i=0;i<T.size();i++)L[++cnt]=(line){T[i].u,T[i].v,0,T[i].k,T[i].id};
	sort(L+1,L+cnt+1);
	for(i=1;i<=cnt;i++){
		if(L[i].id>=1&&L[i].id<=Q){
			t=GetSum(L[i].d);
			if(t>=L[i].k)Q1.push_back((node){L[i].l,L[i].d,L[i].k,L[i].id});
			else Q2.push_back((node){L[i].l,L[i].d,L[i].k-t,L[i].id});
		}
		else{
			Modify(L[i].d,L[i].k);
			Modify(L[i].u+1,-L[i].k);
		}
	}
	Solve(l,mid,Q1);
	Solve(mid+1,r,Q2);
}

int main(){
	int i,x,y,a,b,c,d,lca;
	N=_R();P=_R();Q=_R();
	for(i=1;i<N;i++){
		x=_R();y=_R();
		Add(x,y);Add(y,x);
	}
	DFS(1,0);
	for(i=1;i<=P;i++){
		a=_R();b=_R();c=_R();
		lca=LCA(a,b);
		if(lca==a||lca==b){
			if(dep[a]<dep[b])swap(a,b);
			d=gf(a,dep[a]-dep[b]-1);
			A[++cnt]=rec(In[a],Out[a],1,In[d]-1,c);
			if(Out[d]+1<=N)A[++cnt]=rec(In[a],Out[a],Out[d]+1,N,c);
		}
		else A[++cnt]=rec(In[a],Out[a],In[b],Out[b],c);
	}
	sort(A+1,A+cnt+1,cmpv);
	for(i=1;i<=Q;i++){
		x=_R();y=_R();a=_R();
		if(In[x]>In[y])swap(x,y);
		qry.push_back((node){In[x],In[y],a,i});
	}
	Solve(1,cnt,qry);
	for(i=1;i<=Q;i++)printf("%d\n",Ans[i]);
}